package tree;

/**
 * @Author wangj
 * @Date 2022/4/27 23:03
 */
public class HeroNodeTree {

    private int id;
    private String name;
    private HeroNodeTree left;
    private HeroNodeTree right;

    public HeroNodeTree(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNodeTree getLeft() {
        return left;
    }

    public void setLeft(HeroNodeTree left) {
        this.left = left;
    }

    public HeroNodeTree getRight() {
        return right;
    }

    public void setRight(HeroNodeTree right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNodeTree{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前序遍历
     */
    public void perOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.perOrder();
        }

        if(this.right != null){
            this.right.perOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if(this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null){
            this.right.infixOrder();
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder(){
        if(this.left != null){
            this.left.postOrder();
        }
        if(this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

    /**
     * 前序遍历查找
     * @param no
     * @return
     */
    public HeroNodeTree perSearchNode(int no){
        System.out.println("pre");
        // 先判断当前节点是否相等
        if(this.getId() == no){
            return this;
        }
        HeroNodeTree node = null;
        // 向左递归查找
        if(this.getLeft() != null){
            node = this.getLeft().perSearchNode(no);
        }
        if(node != null){
            return node;
        }
        // 没有找到，向右递归查找
        if(this.getRight() != null){
            node = this.getRight().perSearchNode(no);
        }
        return node;
    }

    /**
     * 中序遍历查找
     * @param no
     * @return
     */
    public HeroNodeTree infixSearchNode(int no){
        HeroNodeTree node = null;
        // 向左递归查找
        if(this.getLeft() != null){
            node = this.getLeft().infixSearchNode(no);
        }
        if(node != null){
            return node;
        }
        // 判断当前节点是否相等
        System.out.println("infix");
        if(this.getId() == no){
            return this;
        }
        // 没有找到，向右递归查找
        if(this.getRight() != null){
            node = this.getRight().infixSearchNode(no);
        }
        return node;
    }

    /**
     * 后序遍历查找
     * @param no
     * @return
     */
    public HeroNodeTree postSearchNode(int no){
        HeroNodeTree node = null;
        // 向左递归查找
        if(this.getLeft() != null){
            node = this.getLeft().postSearchNode(no);
        }
        if(node != null){
            return node;
        }
        // 没有找到，向右递归查找
        if(this.getRight() != null){
            node = this.getRight().postSearchNode(no);
        }

        if(node != null){
            return node;
        }
        // 判断当前节点是否相等
        System.out.println("post");
        if(this.getId() == no){
            return this;
        }
        return node;
    }

    /**
     * 当是叶子节点，则直接删除
     * 当是非叶子节点，则删除整个子树
     */
    public void delNode(int no){

        if(this.getLeft() != null && this.getLeft().getId() == no){
            this.setLeft(null);
            return;
        }

        if(this.getRight() != null && this.getRight().getId() == no){
            this.setRight(null);
            return;
        }
        if(this.getLeft() != null){
            this.getLeft().delNode(no);
        }
        if(this.getRight() != null){
            this.getRight().delNode(no);
        }
    }

    /**
     * 如果删除的节点有左右子树，则用左子树代替要删除节点
     * 如果删除的节点只有一个子节点，则直接替代要删除的节点
     * @param no
     */
    public void delReplaceNode(int no){
        if(this.getLeft() != null && this.getLeft().getId() == no){
            if(this.getLeft().getLeft() != null && this.getLeft().getRight() != null){
                this.getLeft().getLeft().setRight(this.getLeft().getRight());
                this.setLeft(this.getLeft().getLeft());
            }
            return;
        }

        if(this.getRight() != null && this.getRight().getId() == no){
            if(this.getRight().getLeft() != null && this.getRight().getRight() != null){
                this.getRight().getLeft().setRight(this.getRight().getRight());
                this.setRight(this.getRight().getLeft());
            }
            return;
        }
        if(this.getLeft() != null){
            this.getLeft().delReplaceNode(no);
        }
        if(this.getRight() != null){
            this.getRight().delReplaceNode(no);
        }
    }
}
